package s7_查找算法.search2_二分查找;

import s6_排序算法.BaseSort;
import s6_排序算法.sort1_交换排序.QuickSort;
import s7_查找算法.BaseSearch;

import java.util.Arrays;


/**
 * <code>{@link BinarySearch}</code>
 * <p>
 * description: BinarySearch2
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/15 22:12
 *
 * 二分查找递归模式
 */
public class BinarySearch extends BaseSearch {

    public static void main(String[] args) {
        int[] arr = BaseSort.normal();
        System.out.println(Arrays.toString(arr));
        new QuickSort().asc(arr);
        System.out.println(Arrays.toString(arr));


        int target = 2;
        int search = new BinarySearch().search(arr, target);
        System.out.println(search);
    }

    /**
     * 二分查找的递归实现
     * @param arr
     * @param target
     * @return
     */
    public int search(int[] arr, int target) {
        int left =0, right=arr.length-1;
        return search(arr, target, left, right);
    }

    private int search(int[] arr, int target, int left, int right) {
        if(left > right) return -1;
        int mid = (left+right)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) {
            return search(arr, target, left, mid-1);
        } else {
            return search(arr, target, mid+1, right);
        }
    }
}
